进制转换：
十进制转化成其他进制：短除法
其他进制转化成十进制：秦九韶算法
其他进制转化成其他进制
(1) 用十进制过渡
(2) 短除法
短除法
char get(int x)
{
    if(x<=9) return x+'0';//注意+'0'
    else return x-10+'A';
}

string base(int n,int b)//n的b进制表示
{
    string res;
    while(n)
    {
        res+=get(n%b);//mark
        n/=b;
    }
    reverse(res.begin(),res.end());
    return res;
}

试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数
//复杂度为根号n
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
//性质：d可以整除n，那么（n/d）也可以整除n，质数都是成对存在的
//等价于i*i<=x,但是这样i有溢出的风险


试除法分解质因数 —— 模板题 AcWing 867. 分解质因数
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;//质数和次数
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
//分解时数中最多只包含一个大于根号n的质因子（如果有两个那么相乘大于n）
//先枚举小于等于根号n的

快速分解质因数
使用线性筛的方法，并在每次筛的过程中，记录下每个数的最小质因数。
那么在分解质因数的时候，只需要不断除以当前数的最小质因数，就可以快速得到分解的质因数了


朴素筛法求素数 —— 模板题 AcWing 868. 筛质数//O（nloglogn）
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;//优化，只需要筛去素数的倍数
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
//只需要把质数的倍数筛去即可


线性筛法求素数 —— 模板题 AcWing 868. 筛质数//筛法只能筛[1,n]，不能筛任意的[l,r]
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;//primes[j]一定是i的最小质因子，因为primes从小到大枚举
        }
    }
}
//1.i%pj==0
//pj一定是i的最小质因子，pj一定是pj*i的最小质因子
//2.i%pj！=0
//pj小于i的最小质因子，pj也一定是pj*i的最小质因子
//每一个数都会被筛去，用最小质因数来筛


试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
//与求质数相同，同样相匹配的有两个，同样只需要枚举到根号n

通过筛法求出1到n的所有约数之和,O(nlogn)
for(int i = 1;i <= n;i ++) //O(n)
{
    for(int j = 2;j <= n / i;j ++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
    {
        sum[i * j] += i;
    }
}

约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
//ll sum=(sum+1)*p,来求每一个括号内的值

//x=gcd(0,x);
//gcd(a,b)=c 时间复杂度为O(log(a/c))
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
//引理：给定a，b若d=gcd(a,b)>1,则一定不能凑出最大数
//该引理可以推广到n个数的gcd,可能存在任意两个数的gcd>1,但是n个数的gcd=1
//2*3，2*5，3*5
//lcm(a,b)=a/gcd(a,b)*b 此写法求最小公倍数 防止爆long long 

//如果 a,b 均是正整数且互质，那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 (a−1)(b−1)−1
//裴蜀定理 若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
//更相减损术：gcd(a,b)=gcd(a,b−a)，推广到多个数(a,b,c)=(a,b−a,c−b)
求欧拉函数 —— 模板题 AcWing 873. 欧拉函数
//欧拉函数（Euler's totient function），即表示的是小于等于x和x互质的数的个数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);//细节的地方先除后乘，防止爆int 
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}


筛法求欧拉函数 —— 模板题 AcWing 874. 筛法求欧拉函数
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{   
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}
//因为primes[j]是j的最小质因数，所以primes[j]*i分解所得的质因数与i相同，只是公式中的N不同
//如果primes[j]不是j的最小质因数，那么primes[j]*i的欧拉函数值就要在i的基础上乘上primes[j]和（1-1/primes[j]）
//同样是线性筛法筛素数的方法
“龟速乘”——将乘法O（1）的操作变成了O（logn），但是没有直接相乘溢出的风险
用加法实现乘法
int qmul(int a,int k,int b)
{
    int res=0;
    while(k)
    {
        if(k&1) res=(res+a)%b;
        a=(a+a)%b;
        k>>=1;
    }
    return res;
}

快速幂 —— 模板题 AcWing 875. 快速幂
求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;//细节 res=1%p 考虑到了p=1 k=0 的特殊情况
    while (k)
    {
        if (k&1) res = (LL)res * t % p;//细节保证取模之前即使爆int也没事,也可以将res，t类型初始化为LL
        t = (LL)t * t % p;
        k >>= 1;
    }
    return res;
}
//反复平方，不断处理出m^(2^0)%p,m^(2^1)%p,m^(2^2)%p.....m^(2^logk)%p
//根据k的二进制中1的情况选择性乘上

如果幂为负数，则底数取一下倒数即可
double myPow(double x, int n) {
    if (n == 0) return 1;
    long long N = n;
    if (n < 0) {
        x = 1/x;
        N = -N;
    }
    double res = 1;
    while (N > 0) {
        if ((N & 1) == 1) {
            res = res * x;
        }
        x *= x;
        N >>= 1;
    }
    return res;
}

矩阵快速幂
void multi(ll A[], ll B[][N]) // 计算方阵 B 乘向量 A，并将结果储存在 A 中
{
    ll ans[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < N; i ++ )
        A[i] = ans[i] % m;
}

void multi(ll A[][N], ll B[][N]) // 计算方阵 A * B，并将结果储存在 A 中
{
    ll ans[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            A[i][j] = ans[i][j] % m;
}

while (n)// 矩阵快速幂
{
    if (n & 1) multi(S, A);
    multi(A, A);
    n >>= 1;
}
作者：垫底抽风
链接：https://www.acwing.com/solution/content/15121/

矩阵乘法
A(m*n)*B(n*p)->C(m*p)
for(int k=1;k<=n;k++)
    for(int i=1;i<=m;i++)
        for(int j=1;j<=p;j++)
            c[i][j]+=a[i][k]*b[k][j];

对于n*m的矩阵，它的单位矩阵大小为m*m，对于m*n的矩阵，它的单位矩阵大小为n*n

斐波拉契数列矩阵加速
#include <bits/stdc++.h>
using namespace std;

const int N=1e2+5,mod=1e9+7;
long long n;
struct Matrix{
    int n,m;//行列
    long long mat[N][N];     //一定要用long long存矩阵，否则在过程中会爆掉
    void init(){
        memset(mat,0,sizeof(mat));
    }
    void build(){     //建造单位矩阵
        for(int i=1;i<=n;++i)
            mat[i][i]=1;
    }
    Matrix operator *(const Matrix x)const{     //重载运算符
        Matrix res={n,x.m};
        res.init();
        for(int k=1;k<=m;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=x.m;++j)
                    res.mat[i][j]=(res.mat[i][j]+mat[i][k]*x.mat[k][j]%mod)%mod;
        return res;
    }
}st,f;

Matrix ksm(Matrix x,long long w)
{
    Matrix s={x.m,x.m};
    s.init();
    s.build();

    while(w)
    {
        if(w&1)
            s=s*x;//递推快速幂，与普通的递推快速幂无异，但*不能缩写为*=
        x=x*x;
        w>>=1;
    }
    return s;
}

int main(){

    cin >>n;
    if(n<3)//特殊处理
        return cout <<1<<endl,0;

    st.n=2,st.m=1;
    st.mat[1][1]=1,st.mat[2][1]=1;

    f.n=f.m=2;
    f.mat[1][1]=1,f.mat[1][2]=1;
    f.mat[2][1]=1,f.mat[2][2]=0;
    st=ksm(f,n-2)*st;
    cout <<st.mat[1][1]%mod<<endl;

    return 0;
}

Miller Rabin素性检验
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll qmul(ll a,ll b,ll mod)//快速乘
{
    ll c=(ld)a/mod*b;
    ll res=(ull)a*b-(ull)c*mod;
    return (res+mod)%mod;
}
ll qpow(ll a,ll n,ll mod)//快速幂
{
    ll res=1;
    while(n)
    {
        if(n&1) res=qmul(res,a,mod);
        a=qmul(a,a,mod);
        n>>=1;
    }
    return res;
}
bool MRtest(ll n)//Miller Rabin Test
{
    if(n<3||n%2==0) return n==2;//特判
    ll u=n-1,t=0;
    while(u%2==0) u/=2,++t;
    ll ud[]={2,325,9375,28178,450775,9780504,1795265022};
    for(ll a:ud)
    {
        ll v=qpow(a,u,n);
        if(v==1||v==n-1||v==0) continue;
        for(int j=1;j<=t;j++)
        {
            v=qmul(v,v,n);
            if(v==n-1&&j!=t){v=1;break;}//出现一个n-1，后面都是1，直接跳出
            if(v==1) return 0;//这里代表前面没有出现n-1这个解，二次检验失败
        }
        if(v!=1) return 0;//Fermat检验
    }
    return 1;
}
另一种写法：
#include <bits/stdc++.h>
typedef long long LL;
LL fast_pow(LL x,LL y,int m){   //快速幂取模：x^y mod m
    LL res = 1;
    while(y) {
        if(y&1) res*=x, res%=m;
        x*=x, x%=m;
        y>>=1;
    }
    return res;
}

bool witness(LL a, LL n){       // Miller-Rabin素性测试。返回true表示n是合数
        LL u = n-1; 
        int t = 0;              // n-1的二进制，是奇数u的二进制，后面加t个零
        while(u&1 ==0) u = u>>1, t++;    // 整数n-1末尾有几个0，就是t
        LL x1, x2;
        x1 = fast_pow(a,u,n);            // 先计算  a^u mod n
        
        for(int i=1; i<=t; i++) {        // 做t次平方取模
            x2 = fast_pow(x1,2,n);       // x1^2 mod n
            if(x2 == 1 && x1 != 1 && x1 != n-1) return true;  //用推论判断
            x1 = x2;
        }
        if(x1 != 1) return true;         //最后用费马测试判断是否为合数
        return false;
}

int miller_rabin(LL n,int s){            //对n做s次测试
    if(n<2)  return 0;  
    if(n==2) return 1;                   //2是素数
    if(n % 2 == 0 ) return 0;            //偶数

    for(int i = 0;i < s && i < n;i++){   //做s次测试
        LL a = rand() % (n - 1) + 1;     //基值a是随机数
        if(witness(a,n))  return 0;      //n是合数，返回0                           
    }
    return 1;                            //n是素数，返回1
}

int main(){
    int m;                   
    while(scanf("%d",&m) != EOF){
        int cnt = 0;
        for(int i = 0; i < m; i++){
            LL n; scanf("%lld",&n);   
            int s = 50;               //做s次测试
            cnt += miller_rabin(n,s);
        } 
        printf("%d\n",cnt);
    } 
    return 0;
}

pollard_rho定理
//poj 1811题：输入一个整数n,2<=N<2^54，判断它是否为素数，如果不是，输出最小素因子。

typedef long long ll;
ll factor[N],tol;
ll Gcd (ll a,ll b){  return b? Gcd(b, a%b):a;}

ll pollard_rho (ll n){       //返回一个因子，不一定是素因子
    ll i=1, k=2;
    ll c = rand()%(n-1)+1;
    ll x = rand()%n;
    ll y = x;
    while (true){
        i++;
        x = (mult_mod(x,x,n)+c) % n;   //mult_mod(x,x,n)功能是(x*x) mod n
        ll d = Gcd(y>x?y-x:x-y, n);    //重要：保证gcd的数大于等于0
        if (d!=1 && d!=n) return d;    //算出一个因子 
        if (y==x) return n;            //已经出现过，直接返回
        if (i==k) { y=x; k=k<<1;}
    }
}
void findfac (ll n){                   //找所有的素因子
    if (miller_rabin(n)) {             //用miller_rabin判断是否为素数
        factor[tol++] = n;             //存素因子
        return;
    }
    ll p = n;
    while (p>=n) 
        p = pollard_rho(p);            //找到一个因子
    findfac(p);                        //继续寻找更小的因子
    findfac(n/p);
}

求最大因子（记忆化解决）
unordered_map<ll, ll> um;
ll max_prime_factor(ll x)
{
    if (um.count(x))
        return um[x];
    ll fac = Pollard_Rho(x);
    if (fac == 1)
        um[x] = x;
    else
        um[x] = max(max_prime_factor(fac), max_prime_factor(x / fac));
    return um[x];
}

实例：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int factor[10000],tol;

ll Gcd (ll a,ll b){  return b? Gcd(b, a%b):a;}

ll qmul(ll a,ll b,ll mod)//快速乘
{
    ll c=(ld)a/mod*b;
    ll res=(ull)a*b-(ull)c*mod;
    return (res+mod)%mod;
}

ll pollard_rho (ll n){       //返回一个因子，不一定是素因子
    ll i=1, k=2;
    ll c = rand()%(n-1)+1;
    ll x = rand()%n;
    ll y = x;
    while (true){
        i++;
        x = (qmul(x,x,n)+c) % n;   //mult_mod(x,x,n)功能是(x*x) mod n
        ll d = Gcd(y>x?y-x:x-y, n);    //重要：保证gcd的数大于等于0
        if (d!=1 && d!=n) return d;    //算出一个因子 
        if (y==x) return n;            //已经出现过，直接返回
        if (i==k) { y=x; k=k<<1;}
    }
}

ll qpow(ll a,ll n,ll mod)//快速幂
{
    ll res=1;
    while(n)
    {
        if(n&1) res=qmul(res,a,mod);
        a=qmul(a,a,mod);
        n>>=1;
    }
    return res;
}

bool MRtest(ll n)//Miller Rabin Test
{
    if(n<3||n%2==0) return n==2;//特判
    ll u=n-1,t=0;
    while(u%2==0) u/=2,++t;
    ll ud[]={2,325,9375,28178,450775,9780504,1795265022};
    for(ll a:ud)
    {
        ll v=qpow(a,u,n);
        if(v==1||v==n-1||v==0) continue;
        for(int j=1;j<=t;j++)
        {
            v=qmul(v,v,n);
            if(v==n-1&&j!=t){v=1;break;}//出现一个n-1，后面都是1，直接跳出
            if(v==1) return 0;//这里代表前面没有出现n-1这个解，二次检验失败
        }
        if(v!=1) return 0;//Fermat检验
    }
    return 1;
}

void findfac (ll n){                   //找所有的素因子
    if (MRtest(n)) {             //用miller_rabin判断是否为素数
        factor[tol++] = n;             //存素因子
        return;
    }
    ll p = n;
    while (p>=n) 
        p = pollard_rho(p);            //找到一个因子
    findfac(p);                        //继续寻找更小的因子
    findfac(n/p);
}

int main(){
    ll m;                   
    
    cin >>m;
    
    findfac(m);
    
    for(int i=0;i<tol;i++)
        cout <<factor[i]<<endl;
    
    return 0;
}

乘法逆元的定义
若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b^(−1)(mod m)。
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，b^(m−2)即为b的乘法逆元。
特别注意：在模数意义下模数不存在逆元

扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法//也求出了d
// 求x, y，使得ax + by = gcd(a, b) = d
int exgcd(int a, int b, int &x, int &y)//注意x,y的类型为引用
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);//by+（a mod b)x=d,ax+b(y-(a/b)x)=d
    //求解b和a%b的系数转化为求解a和b的系数，当上面的递归结束的时候就已经得到满足条件by+（a mod b)x=d的x,y
    y -= (a/b) * x;
    return d;//d为gcd（a,b）
}
//定理可用于求解线性同余方程，如ai∗xi≡bi(mod mi)，即存在一个y，a*x-m*y=b
//有解当且仅当(a,m)|b
//先用扩展欧几里得算法求出一组整数 x0,y0 使得 a∗x0+m∗y0=gcd(a,m) 
//然后 x=x0∗b/gcd(a,m)%m即是所求，根据题目要求的ai∗xi≡bi(modmi),只有x%m这个等式才依然成立.

高斯消元 —— 模板题 AcWing 883. 高斯消元解线性方程组
//求解n个变量n个方程的多元方程组，解有三种情况：无解，无穷多组解，唯一解
// a[N][N]是增广矩阵
//矩阵经过初等行列变换为“倒三角”的完美阶梯形（有唯一解），若不为完美阶梯形且出现左边为0右边不为零的等式（无解）
//出现式子0=0（无穷多个解）
int gauss()
{
    int c, r;//c列，r行
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;//如果绝对值最大为0

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前上的首位变成1，从后往前除，保证第c列最后为1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)//该行的b值为0
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}
//枚举每一列c，找到绝对值最大的一行，将该行交换到最上面，将该行全部数除以一个数使得第一个数变为1
//将下面所有行的第c列消成0，此时第一行就固定了，之后找绝对值最大的一行从第二行开始

//变成完美阶梯形后，将最后一行整体变换使得系数变为1
//然后用这个1，使得上面行的对应列为0，然后用倒数第二行为1的列对应操作
//最后每一行b的值就是xi

//十万组数据，1<=b<=a<=2000，O(N^2)
递归法求组合数 —— 模板题 AcWing 885. 求组合数 I
// c[a][b] 表示从a个苹果中选b个的方案数，会爆long long,根据题意取模mod
//c[a][b]=c[a-1][b]+c[a-1][b-1]，就是a-1个物品对于第b个物品选择或者不选
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
//预处理，打表

//排列数
void get_A()
{
    a[0][0] = 1;
    for (int i = 1; i <= 2000; ++i)
    {
        a[i][0] = 1;
        for (int j = 1; j <= i; ++j)
        {
            a[i][j] = a[i][j-1] * (i-j+1) % mod;
        }
    }
}

//一万组数据，1<=b<=a<=1e5,O(nlogn)
通过预处理逆元的方式求组合数 —— 模板题 AcWing 886. 求组合数 II
首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数（比如1e9+7），可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
// fact[]以及infact[]都需要是long long类型
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
//c[a][b]=fact[a]*infact[b]%mod*infact[a-b]%mod;


//二十组数据，1<=b<=a<=1e18,1<=p<=1e5
//c[a][b]=c[a mod p][b mod p]*c[a/p][b/p](mod p),递归求解（a,b小于p时，采用第二种方法求解）
Lucas定理 —— 模板题 AcWing 887. 求组合数 III
若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k)       // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b)     // 通过定理求组合数C(a, b)
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}

int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

预处理阶乘的版本（更快）：
const int maxm = 2e5 + 7;
const int mod  = 110119;

ll fac[maxm], refac[maxm];

ll qmi(ll a, ll p, ll mo){
    ll ret = 1;
    while(p){
        if(p & 1) ret = ret * a % mo;
        a = a * a % mo;
        p >>= 1;
    }
    return ret;
}

void init(){
    refac[0] = refac[1] = fac[0] = fac[1] = 1LL;
    for(int i = 2; i < mod; i ++) fac[i] = 1LL * fac[i - 1] * i % mod;
    refac[mod - 1] = qmi(fac[mod - 1], mod - 2, mod);
    for(int i = mod - 2; i > 0; i --) refac[i] = 1LL * refac[i + 1] * (i + 1) % mod;
}

ll C(int a, int b){
    if(a < b) return 0;
    return fac[a] * refac[b] % mod * refac[a - b] % mod;
}

ll lucas(ll n, ll m){
    if(!m) return 1;
    return C(n % mod, m % mod) * lucas(n/mod, m/mod) % mod;
}


分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...//p的倍数+p^2的倍数+p^3的倍数....
    //然后将分子中p的次数减去分母中p的次数
    3. 用高精度乘法将所有质因子相乘

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉


void get_primes(int n)      // 线性筛法求素数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)       // 求n！中的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

get_primes(a);  // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{
    int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

整数分块
//求n除以1-n向下取整的和
#include <cstdio>
typedef long long ll;
ll solve() {
    ll n, ans = 0;
    scanf("%lld", &n);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);  //关键操作
        ans += n / l * (r - l + 1);
    }
    return ans;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) printf("Case %d: %lld\n", i, solve());
}



卡特兰数 —— 模板题 AcWing 889. 满足条件的01序列
给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ......
应用
二叉树的计数：已知二叉树有 n 个结点，求能构成多少种不同的二叉树
括号化问题：一个合法的表达式由()包围，()可以嵌套和连接，如：(())()也是合法表达式，现给出 n 对括号，求可以组成的合法表达式的个数
划分问题：将一个凸 n+2 多边形区域分成三角形区域的方法数
出栈问题：一个栈的进栈序列为1,2,3,...n，求不同的出栈序列有多少种
路径问题：在 n*n 的方格地图中，从一个角到另外一个角，求不跨越对角线的路径数有多少种
握手问题：2n 个人均匀坐在一个圆桌边上，某个时刻所有人同时与另一个人握手，要求手之间不能交叉，求共有多少种握手方法

//问题转换为从坐标（0，0）走到（n，n）,0：向右走一格，1：向上走一格，那么n个0和n个1组成的序列代表了坐标中的一种走法
//任意前缀中0的个数都不少于1的个数：任意时刻坐标x>=y
//没有限制总步数：c(2n,n),限制不能经过y=x+1这条线，两者相减就是答案
//假设n=6.那么（6，6）关于限制线的对称点为（5，7）,从（0，0）到（5，7）必然经过限制线，那么路径与限制线的第一个交点之后的路径
//作限制线的轴对称，得到的就是（0，0）到（6，6）经过限制线的一条路径，轴对称的前后次数是对应的
//答案就是c(12,6)-c(12,5)——c(12,5)是从（0，0）到（5，7）的路径数

//卡特兰数c(2n,n)-c(2n,n-1)=C(2n, n) / (n + 1)
//注意，所有的除法都要转换成逆元， 不仅c几几，除n-1也要转换

NIM游戏 —— 模板题 AcWing 891. Nim游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

先手必胜状态在行动之后就是先手必败状态

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0
//先手必败的一种，所有Ai为0，A1 ^ A2 ^ … ^ An = 0
//如果不为0，可以通过变换（某一堆拿走一些石子）使之为0
证明：设A1 ^ A2 ^ … ^ An 为x，x不等于0，x的二进制表示中最高一位1在第k位，A1-An中必然有一个Ai,Ai的第k位是1
Ai ^ x <Ai , Ai-(Ai-(Ai ^ x))=Ai ^ x (相当于第Ai堆拿走一些物品)，A1 ^ A2 ^ …（Ai ^ x） ^ An=x^x=0
A1 ^ A2 ^ …Ai ^ An为0之后，又第Ai堆拿走一些物品，A1 ^ A2 ^ …Ai次 ^ An 不为0
因为拿走物品前后两者相乘，如果A1 ^ A2 ^ …Ai次 ^ An为0，那么可以推出Ai ^ Ai次=0,但Ai 不等于 Ai次 ，推出矛盾



公平组合游戏ICG
若一个游戏满足：

由两名玩家交替行动；
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S

SG函数
在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk
定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。
SG（终点）=0

定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

SG函数值不等于0，说明该点是可以到达0的，任何一个非0的状态都是可以到达0的
终止状态为0  ，先手SG不为0，后手SG可以到达0，终止状态一定被后手遇到，先手SG为0，后手SG一定不为0


组合博弈，sg函数的应用
有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏
设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。
G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
证明方法和NIM一样

题目描述
给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

//记忆化搜索实现sg函数

#include <iostream>
#include <unordered_set>
#include <cstring>

using namespace std;

const int N = 110 , M = 10010;

int n , m;
int s[N] , f[M];

int sg(int x)
{
    if(f[x] != -1) return f[x];//记忆化搜索，如果f[x]已经被计算过，则直接返回

    unordered_set<int> S;//用一个哈希表来存每一个局面能到的所有情况，便于求mex

    for(int i = 0 ; i < m ; i++)
        if(x >= s[i]) S.insert(sg(x - s[i]));//如果可以减去s[i]，则添加到S中

    for(int i = 0 ; ; i++)//求mex()，即找到最小并不在原集合中的数
        if(!S.count(i)) return f[x] = i;

}

int main()
{
    cin >> m;
    for(int i = 0 ; i < m ; i++)    cin >> s[i];

    memset(f , -1 , sizeof f);

    cin >> n;
    int res = 0;
    while(n--)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }


    if(res) puts("Yes");
    else puts("No");
    return 0;
}


nim游戏+可将一堆石子分为三堆不为零的石子的操作
int sg[N];
bool st[N];

void init(){
    sg[0]=0;
    for(int i=1;i<=200;i++){
        memset(st,0,sizeof(st));
        for(int j=1;j<=i;j++){
            for(int k=1;k<=i;k++){
                if((j>0)&&(k>0)&&((i-j-k)>0)){
                    st[sg[j]^sg[k]^sg[i-j-k]]=1;
                }
            }
        }
        for(int j=0;j<i;j++) st[sg[j]]=1;
        for(int j=0;;j++){
            if(!st[j]){
                sg[i]=j;
                break;
            }
        }
    }
}

模板一打表：
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];     
void getSG(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(hash,0,sizeof(hash));
        for(j=1;f[j]<=i;j++)
            hash[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++)    //求mes{}中未出现的最小的非负整数
        {
            if(hash[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}

模板二：DFS
//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
int SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

作者：Anoxia_3
链接：https://www.acwing.com/solution/content/13191/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

向上取整转向下取整：⌈ m/n ⌉ = ⌊ (m−1)/n ⌋ + 1 

1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6
偶数平方和：
2^2+4^2+6^2+.+(2n)^2
=4*1^2+4*2^2+4*3^2+...+4*n^2
=4(1^2+2^2+3^2+...+n^2)
=4*n(n+1)(2n+1)/6
=2n(n+1)(2n+1)/3

一个两个数与、两个数或之间的性质：
a+b=(a&b)+(a|b)

FFT
/*给定一个 n 次多项式 F(x)=a0+a1x+a2x2+…+anxn。
以及一个 m 次多项式 G(x)=b0+b1x+b2x2+…+bmxm。
已知 H(x)=F(x)⋅G(x)=c0+c1x+c2x2+…+c(n+m)x(n+m)。
第一行包含两个整数 n,m。
第二行包含 n+1 个整数 a0,a1,…,an。
第三行包含 m+1 个整数 b0,b1,…,bn。
请你计算并输出 c0,c1,…,cn+m*/

/*
如果多项式次数为负数，那么对于次数加上一个偏移量（可以是n，m可能取值的最大值），如b[M-x]表示次数为-x的情况
遍历所有次数i时需要减去偏移量(i-M)
因为加上了偏移量（改变了最大次幂），N的值需要扩大,相应的limit的值也需要改变
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 300007;//选择一个大于n+m的最小2的整数次幂的数

const double PI = acos(-1);

int n, m;
int limit = 1;//
int L;//二进制的位数
int R[N];

inline int read()
{
    register int x = 0, f = 1;
    register char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

struct Complex
{
    double x, y;//实部和虚部
    Complex (double x = 0, double y = 0) : x(x), y(y) { }
}a[N], b[N];//数组下标为i，那该下标表示幂次为i

Complex operator * (Complex J, Complex Q) {
    //模长相乘，幅度相加
    return Complex(J.x * Q.x - J.y * Q.y, J.x * Q.y + J.y * Q.x);
}
Complex operator - (Complex J, Complex Q) {
    return Complex(J.x - Q.x, J.y - Q.y);
}
Complex operator + (Complex J, Complex Q) {
    return Complex(J.x + Q.x, J.y + Q.y);
}

void FFT(Complex * A, int type)
{
    for(int i = 0; i < limit; ++ i)
        if(i < R[i])
            swap(A[i], A[R[i]]);
        //i小于R[i]时才交换，防止同一个元素交换两次，回到它原来的位置。

    //从底层往上合并
    for(int mid = 1; mid < limit; mid <<= 1) {
        //待合并区间长度的一半，最开始是两个长度为1的序列合并,mid = 1;
        Complex wn(cos(PI / mid), type * sin(PI / mid));//单位根w_n^1;

        for(int len = mid << 1, pos = 0; pos < limit; pos += len) {
            //len是区间的长度，pos是当前的位置,也就是合并到了哪一位
            Complex w(1, 0);//幂,一直乘，得到平方，三次方...

            for(int k = 0; k < mid; ++ k, w = w * wn) {
                //只扫左半部分，蝴蝶变换得到右半部分的答案,w 为 w_n^k
                Complex x = A[pos + k];//左半部分
                Complex y = w * A[pos + mid + k];//右半部分
                A[pos + k] = x + y;//左边加
                A[pos + mid + k] = x - y;//右边减
            }
        }
    }
    if(type == 1) return ;
    for(int i = 0; i <= limit; ++ i)
        a[i].x /= limit;
        //最后要除以limit也就是补成了2的整数幂的那个N，将点值转换为系数
        //（前面推过了点值与系数之间相除是N）
}

int main()
{
    n = read(), m = read();
    //读入多项式的每一项，保存在复数的实部
    for(int i = 0; i <= n; ++ i)
        a[i].x = read();
    for(int i = 0; i <= m; ++ i)
        b[i].x = read();
    while(limit <= n + m)//如果不知道结果最高次，那么n+m替换为n可能取值的最大值+m可能取值的最大值
        limit <<= 1, L ++ ;
    //也可以写成：limit = 1 << int(log2(n + m) + 1); 
    // 补成2的整次幂，也就是N
    for(int i = 0; i < limit; ++ i)
        R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
    FFT(a, 1);//FFT 把a的系数表示转化为点值表示
    FFT(b, 1);//FFT 把b的系数表示转化为点值表示
    //计算两个系数表示法的多项式相乘后的点值表示
    for(int i = 0; i <= limit; ++ i)
        a[i] = a[i] * b[i];
    //对应项相乘，O(n)得到点值表示的多项式的解C，利用逆变换完成插值得到答案C的点值表示
    FFT(a, -1);

    for(int i = 0; i <= n+m; ++ i)//如果不知道结果最高次，那么n+m替换为limit
        //这里的 x 和 y 是 double 的 hhh
        printf("%d ", (int)(a[i].x + 0.5));//注意要+0.5，否则精度会有问题
    return 0;
}


BM算法用于求解常系数线性递推式。它可以在 O(n^2) 的时间复杂度内解决问题。
如果是打表找线性递推式需要20项以上
/*
给出一个数列 P 从 0 开始的前 n 项，求序列 P 在mod 998244353 下的最短线性递推式，并在mod 998244353 下输出 P_m 
*/
#include<bits/stdc++.h>
#define ll long long
#define lld long ll
using namespace std;
template<typename tn> void read(tn &a){
    tn x=0,f=1; char c=' ';
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    a=x*f;
}
const int N = 10010,mod = 998244353;
ll h[N];
int n,m;
ll fp(ll a,ll k){
    ll ans=1;
    for(;k;k>>=1,a=a*a%mod)
        if(k&1) ans=a*ans%mod;
    return ans;
}
void BM(ll *a,int n,vector<ll>&ans){
    ans.clear();
    vector<ll> lst;
    int w=0;ll delta=0;
    for(int i=1;i<=n;i++){
        ll tmp=0;
        for(int j=0;j<ans.size();j++)
            tmp=(tmp+a[i-1-j]*ans[j])%mod;
        if((a[i]-tmp)%mod==0) continue;
        if(!w){
            w=i;delta=a[i]-tmp;
            for(int j=i;j;j--) ans.push_back(0);
            continue;
        }
        vector<ll> now=ans;
        ll mul=(a[i]-tmp)*fp(delta,mod-2)%mod;
        if(ans.size()<lst.size()+i-w) ans.resize(lst.size()+i-w);
        ans[i-w-1]=(ans[i-w-1]+mul)%mod;
        for(int j=0;j<lst.size();j++) ans[i-w+j]=(ans[i-w+j]-mul*lst[j])%mod;
        if(now.size()-i<lst.size()-w){
            lst=now;w=i;delta=a[i]-tmp;
        }
    }
}
ll calc(int m,vector<ll>&coef,ll*h){
    if(m<=coef.size()) return h[m];
    int k=coef.size();
    static ll f[N],g[N],res[N],p[N];
    p[0]=-1;
    for(int i=1;i<=k;i++) p[i]=coef[i-1];
    for(int i=0;i<=2*k;i++) f[i]=g[i]=0;
    f[0]=1;
    if(k>1) g[1]=1;
    else g[0]=p[0];
    auto mul = [&](ll *a,ll *b,ll *c){
        for(int i=0;i<=2*k;i++) res[i]=0;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                res[i+j]=(res[i+j]+a[i]*b[j])%mod;
        for(int i=2*k;i>=k;i--)
            if(res[i]%mod)
                for(int j=k;~j;j--)
                    res[i-j]=(res[i-j]+res[i]*p[j])%mod;
        for(int i=0;i<2*k;i++) c[i]=res[i];
        return 0;
    };
    for(;m;m>>=1,mul(g,g,g))
        if(m&1) mul(f,g,f);
    ll ans=0;
    for(int i=0;i<k;i++)
        ans=(ans+h[i+1]*f[i])%mod;
    return ans;
}
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)
        read(h[i]);
    vector<ll> ans;
    BM(h,n,ans);
    for(auto x:ans) cout<<(x+mod)%mod<<' ';
    cout<<'\n';
    cout<<(calc(m,ans,h)+mod)%mod<<'\n';
    return 0;
}